{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "# 走迷宫",
   "id": "8b0a95cae96db336"
  },
  {
   "cell_type": "code",
   "id": "initial_id",
   "metadata": {
    "collapsed": true,
    "ExecuteTime": {
     "end_time": "2025-03-17T11:17:43.784038Z",
     "start_time": "2025-03-17T11:17:43.765833Z"
    }
   },
   "source": [
    "#能出来但是不是最“快”出来的,出来用到的是深度优先遍历，“找最短”需要用到广度优先遍历->队列\n",
    "maze=[\n",
    "    [1,1,1,1,1,1,1,1,1,1],\n",
    "    [1,0,1,1,0,0,0,1,1,1],\n",
    "    [1,0,1,1,1,1,0,0,1,1],\n",
    "    [1,0,1,0,0,0,0,0,1,1],\n",
    "    [1,0,1,0,1,1,1,1,1,1],\n",
    "    [1,0,0,0,1,1,1,1,1,1],\n",
    "    [1,1,1,0,0,0,0,1,1,1],\n",
    "    [1,1,1,0,0,1,0,1,1,1],\n",
    "    [1,1,1,1,1,1,0,0,0,1],\n",
    "    [1,1,1,1,1,1,1,1,1,1],\n",
    "]\n",
    "#设置起点\n",
    "#设置终点\n",
    "start=(1,1)\n",
    "end=(8,8)\n",
    "\n",
    "#判断当前这个点，上下左右是0还是1，如果是01就可以走\n",
    "#下面这个点：r+1,c\n",
    "#右：r,c+1\n",
    "#左：r,c-1\n",
    "#上：r-1,c\n",
    "\n",
    "#栈：先进先出 ：砌墙的砖头，后来者居上\n",
    "\n",
    "lst=[start]  #列表中放的是我每一步走的坐标\n",
    "\n",
    "while lst:\n",
    "    #列表有东西才能继续往下走\n",
    "    #当前走到的节点是哪一个节点\n",
    "    now=lst[-1]\n",
    "    if now==end:\n",
    "        print(\"出来了\")\n",
    "        print(lst)\n",
    "        break\n",
    "    row,col=now #解构，解包 (2，1)  行，列\n",
    "    maze[row][col]=2  #这个点已经走过了，标记一下\n",
    "    #上右下左，邻居们是不是0 如果是0就可以走\n",
    "    \n",
    "    #上方可以走\n",
    "    if maze[row-1][col]==0:\n",
    "        lst.append((row-1,col))\n",
    "        continue\n",
    "        \n",
    "    #右方可以走\n",
    "    elif maze[row][col+1]==0:\n",
    "        lst.append((row,col+1))\n",
    "        continue\n",
    "    \n",
    "    #下方可以走\n",
    "    elif maze[row+1][col]==0:\n",
    "        lst.append((row+1,col))\n",
    "        continue\n",
    "    \n",
    "    #左方可以走\n",
    "    elif maze[row][col-1]==0:\n",
    "        lst.append((row,col-1))\n",
    "        continue\n",
    "    \n",
    "    else:#邻居们不让走\n",
    "        lst.pop() #把最后一个节点推出\n",
    "else:\n",
    "    print(\"迷宫是走不通的\")\n",
    "    "
   ],
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "出来了\n",
      "[(1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (6, 3), (6, 4), (6, 5), (6, 6), (7, 6), (8, 6), (8, 7), (8, 8)]\n"
     ]
    }
   ],
   "execution_count": 14
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "### 解构，解包",
   "id": "41883c682e108b64"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-17T09:40:42.276532Z",
     "start_time": "2025-03-17T09:40:42.262620Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#解包元组\n",
    "point=(1,2)\n",
    "x,y=point\n",
    "print(x,y) #1 2"
   ],
   "id": "8ba2ba85ee161d66",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2\n"
     ]
    }
   ],
   "execution_count": 6
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-17T09:41:41.743794Z",
     "start_time": "2025-03-17T09:41:41.729094Z"
    }
   },
   "cell_type": "code",
   "source": [
    "# 解包列表\n",
    "numbers=[10,20,30]\n",
    "a,b,c=numbers\n",
    "print(a,b,c) #10 20 30"
   ],
   "id": "d59c7727b2f4169",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 20 30\n"
     ]
    }
   ],
   "execution_count": 7
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-17T09:43:01.843683Z",
     "start_time": "2025-03-17T09:43:01.827386Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#解包字符串\n",
    "s=\"abc\"\n",
    "char1,char2,char3=s \n",
    "print(char1,char2,char3) #a b c"
   ],
   "id": "600ee3698236ad81",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a b c\n"
     ]
    }
   ],
   "execution_count": 8
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-17T09:44:56.518390Z",
     "start_time": "2025-03-17T09:44:56.506905Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#扩展解包 将多余的元素收集到一个列表中，使用*来实现\n",
    "numbers=[1,2,3,4,5]\n",
    "first,second,*rest=numbers\n",
    "print(first,second,rest) #1 2 [3,4,5]"
   ],
   "id": "ad1bfc4be19c59ec",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 [3, 4, 5]\n"
     ]
    }
   ],
   "execution_count": 9
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-17T09:46:31.511031Z",
     "start_time": "2025-03-17T09:46:31.501482Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#忽略多余的元素\n",
    "numbers=[1,2,3,4,5]\n",
    "first,second,*_,last=numbers\n",
    "print(first,second,last)  #1 2 5"
   ],
   "id": "1c7d60a8760dbfc2",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 5\n"
     ]
    }
   ],
   "execution_count": 11
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-17T09:49:03.947772Z",
     "start_time": "2025-03-17T09:49:03.938505Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#字典解包\n",
    "#将字典中的键值对快速赋值给变量\n",
    "person={\"name\":\"Alice\",\"age\":25,\"city\":\"New York\"}\n",
    "name,age,city=person.values()\n",
    "print(name,age,city) #Alice 25 New York"
   ],
   "id": "3720fb54ec5495d4",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alice 25 New York\n"
     ]
    }
   ],
   "execution_count": 12
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2025-03-17T09:50:52.548714Z",
     "start_time": "2025-03-17T09:50:52.535381Z"
    }
   },
   "cell_type": "code",
   "source": [
    "#解包字典中的键和值\n",
    "person={\"name\":\"Alice\",\"age\":25,\"city\":\"New York\"}\n",
    "for key,value in person.items():\n",
    "    print(key,value)\n",
    "# name Alice\n",
    "# age 25\n",
    "# city New York"
   ],
   "id": "d4110197687ed981",
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "name Alice\n",
      "age 25\n",
      "city New York\n"
     ]
    }
   ],
   "execution_count": 13
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "# 走迷宫\n",
    "    给定一个N×M的网格迷宫G。G的每个格子要么是道路，要么是障碍物（道路用1表示，障碍物用0表示）。已知迷宫的入口位置为(x1,y1)，出口位置为(x2,y2)。问从入口走到出口，最少要走多少个格子。\n",
    "    输入描述\n",
    "    输入第1行包含两个正整数N,M，分别表示迷宫的大小。接下来输入一个N×M的矩阵。若Gi,j=1 表示其为道路，否则表示其为障碍物。最后一行输入四个整数x1,y1,x2,y2，表示入口的位置和出口的位置。1≤N,M≤10**2，0≤Gi,j≤1，1≤x1,x2≤N，1≤y1，y2<=M\n",
    "    输出描述\n",
    "    输出仅一行，包含一个整数表示答案。若无法从入口到出口，则输出−1。"
   ],
   "id": "a1b30779add93f80"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "#队列 先进先出\n",
    "#道路为1，障碍为0\n",
    "n, m = map(int, input().split())  #读取输入的第一行，包含两个整数 n 和 m，分别表示网格的行数和列数\n",
    "gra = [list(map(int, input().split())) for i in range(n)] #    使用列表推导式读取接下来的 n 行输入，每行包含 m 个整数，表示网格的每个单元格的值。gra 是一个二维列表，表示整个网格。\n",
    "dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] #dirs 是一个二维列表，表示四个可能的移动方向：下，上，右，左   x轴对应列，y轴对应行\n",
    "x1, y1, x2, y2 = map(int, input().split()) #x1, y1, x2, y2，分别表示起点和终点的坐标。坐标从 1 开始，因此在实际使用时需要减去 1，将其转换为从 0 开始的索引。   \n",
    "q = [[x1 - 1, y1 - 1, 0]]  #当前点的坐标和步数。\n",
    "f = True#f 用于标记是否找到终点。初始值为 True，表示尚未找到终点。\n",
    "while q:\n",
    "    x, y, dis = q.pop(0) # 从队列中取出一个状态\n",
    "    if x == x2 - 1 and y == y2 - 1: # 检查是否到达终点\n",
    "        f = False\n",
    "        print(dis) # 输出步数\n",
    "        break\n",
    "    for xx, yy in dirs: # 遍历所有可能的移动方向\n",
    "        tx, ty = xx + x, yy + y # 计算新坐标\n",
    "        if tx >= 0 and tx < n and ty >= 0 and ty < m and gra[tx][ty] == 1: # 检查新坐标是否有效\n",
    "            gra[tx][ty] = 0   # 标记为已访问\n",
    "            q.append([tx, ty, dis+1]) # 将新状态加入队列\n",
    "if f: print(-1)  # 如果未找到终点"
   ],
   "id": "aceb210fc722bd8c"
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
